1. Field of the Invention
The present invention relates to a register allocation system adaptive for pipelining wherein each register is allocated to an associated instruction in a compiler which compiles or translates a program written in a high-order language for programming to output a sequence of machine-oriented words adaptive for pipelining.
2. Description of the Prior Art
The compiler is utilized in order to obtain an executable machine-language program, or an executable format of a program, upon translation of a source program written in a high-order language for programming.
In the compiler, there is provided processing such that the source program is temporarily compiled into an intermediate format program, and then the intermediate format program is further translated into an executable format program.
The intermediate format program comprises pseudo-codes. The pseudo-codes are virtual machine-oriented instructions which are not limited in the number of registers used. A register, which is used to store an operand of an instruction represented by such a pseudo-code, is called a virtual register.
In a case where the intermediate format program is compiled into the executable format program, it is necessary to perform a register allocation processing in which the virtual registers are alloted to real registers which actually exist. This register allocation processing is provided as a sort of back end processing of the compiler, which is a compiler processing from the intermediate format program into the executable format program.
In the register allocation processing, it is desirable to proceed with the processing in such a way that the number of real registers to be used is reduced as much as possible, since the real registers are limited in number.
In the recent CPU (processor) design, pipeline control is performed to increase processing speed. The pipeline control provides control whereby one instruction is divided into a plurality of steps, and during execution of some step of the instruction, some step of another instruction is executed. According to this control, it is possible to execute a plurality of instructions during a unit period of time which formerly permitted, only one instruction to be executed, and thus to increase a processing speed as the whole.
When an execution result of some instruction is used by another instruction, there is occasionally a case where execution of a succeeding instruction is paused until execution of the preceding instruction is completed. These instructions cannot be processed on a parallel basis as in pipeline control, and such an event is called a disturbance of the pipe.
In order to reduce such disturbances of the pipe as little as possible, the compiler performs a so-called optimizing processing of instruction relocation adaptive for pipelining in which the sequence of instructions in the executable format of a program is changed.
According to the conventional compiler, a register allocation processing is performed independently of the optimizing processing of instruction relocation adaptive for pipelining (hereinafter simply referred to as optimizing processing), without having any relationship therebetween.
FIGS. 2A, 2B and 2C are diagrams for explaining the operation of the conventional compiler. Now assuming that a source program as shown in FIG. 2A is compiled into pseudo-codes as shown in FIG. 2B, in pseudo-code (1), the value of "b" is loaded in virtual register VR1. In pseudo-code (2), the value of virtual register VR1 is stored in "a". The pseudo-codes (3)-(6) are likewise produced.
If there is provided register allocation processing such that real registers are alloted to the pseudo-codes as mentioned above, an executable format of program of the machine-oriented language as shown in FIG. 2C is produced. That is, in machine-oriented instruction (1), the value of "b" is loaded in real register r0. In machine-oriented instruction (2), the value of real register r0 is stored in "a". The machine words (3)-(6) are likewise produced.
There is provided, between the machine-oriented words, a relationship such that after completion of execution of the machine language instruction (1), it only permits execution of the machine language instruction (2), after completion of execution of the machine language instruction (3), it only permits the machine language instruction (4) to be executed, and after completion of execution of the machine instruction (5), it only permits execution of the machine-language instruction (6). In other words, after execution of the machine instructions (2) and (4), the values of the real register r0 become unnecessary, respectively. Thus, in the register allocation processing, it is possible to allocate the real register r0 to all of the machine words, so that the real register r0 is most efficiently used.
By the way, in a case there is provided an optimizing for the machine instructions as shown in FIG. 2C, there is not such an occasion that the machine instructions are relocated. The reason is that the real register r0 is allocated to all of the machine or instructions, and thus the execution cannot be performed on a parallel basis. Therefore, the conventional compiler encounters such a problem that disturbances of the pipe, which would occur between each couple of the machine words (1)-(2), (3)-(4) and (5)-(8), cannot be resolved.